1. Field of the Invention
This invention relates to the field of digital systems employing non-volatile memory and particularly flash memory as mass storage for computers, digital cameras and the like.
2. Description of the Prior Art
Recently, solid state memory has gained popularity for use in replacing mass storage units in various technology areas such as computers, modems and the like. For example, in a computer system, hard disk drives are employed to store large amounts of information (i.e., programs, data, and other information) and hard disk drives commonly employ rotating magnetic media for such mass storage. Due to various deficiencies however, in rotating media such as lack of physical durability and high power consumption, flash memory is gaining acceptance to replace the conventional hard disk drive. Additionally, more recent digital systems such as digital cameras and network routers also require large storage areas and have started to use flash memory for the storage of information. It should be noted that EPROM is also suitable as a replacement for systems using flash memory devices but it has lower performance.
Flash memory is generally provided in the form of semiconductor devices (or chips) with each device made of a large number of transistor memory cells and each cell being individually programmable. The programming (or writing) and erasing of such a memory cell is limited to a finite number of erase-write cycles, which basically determines the lifetime of the device. Furthermore, an inherent characteristic of flash memory cells is that they must be erased and verified for successful erase prior to being programmed.
In replacing hard disk drives of computer systems with flash semiconductor memory, one of the requirements for the latter to be successful is that its use in lieu of a rotating media hard disk mass storage device be transparent to the system designer and the user. In other words, the designer of a computer incorporating such a semiconductor mass storage device should be able to simply remove the hard disk and replace it with a semiconductor mass storage. All presently-available commercial software should operate on a system employing such a semiconductor "hard disk" without the necessity of any modification. The problem arises however, that as in flash memory, the area of memory that once contained information must first be erased prior to being re-programmed. Unlike a hard disk device, in a flash memory device, an erase cycle is slow and can significantly reduce the performance of a system utilizing flash memory as its mass storage.
Various approaches such as the use of wear-leveling techniques have been devised to manipulate information being stored into flash memory devices in an effort to minimize the devices' erase-write cycle limitations. U.S. Pat. No. 5,485,595, entitled "Flash Memory Mass Storage Architecture Incorporating Wear Leveling Technique Without Using CAM Cells", issued to Mahmud Assar, Petro Estakhri, Siamack Nemazie and Mahmood Mozaffari on Jan. 16, 1996; U.S. Pat. No. 5,388,083, entitled "Flash Memory Mass Storage Architecture", issued to Mahmud Assar, Siamack Nemazie and Petro Estakhri on Feb. 5, 1995; and U.S. Pat. No. 5,479,638, entitled "Flash Memory Mass Storage Architecture Incorporation Wear Leveling Technique", issued to Mahmud Assar, Siamack Nemazie and Petro Estakhri on Dec. 26, 1995, disclose a number of such approaches using space-management schemes. The specifications of these three patents are herein incorporated by reference.
As is disclosed in the above-cited patents, semiconductor mass storage architecture (such as flash memory devices) has blocks of information (each block may include data and overhead information) sized to conform with commercial hard disk sector sizes. These blocks may be also referred to as pages. A semiconductor memory storage device is arranged into N blocks of data with each block of data being an integer number of bytes long. Block sizes are commonly 512 bytes corresponding with a sector length in a commercially-available hard disk drive, although other sector lengths may be used.
In storing and/or retrieving a data file (data files may be any computer files including commercial software, user program, word processor software document, spread sheet file and the like), a computer (or host) system provides what is referred to as the logical block address indicating the location of where the host believes the data file to exist within the mass storage. Due to the manipulation of data files resulting from space management techniques such as those disclosed in the above-referenced patents, the logical block address is not necessarily the actual address of where the data file may be located. In fact, generally, a controller semiconductor device coupled between the host (in the computer system) and the flash devices translates the logical block address (LBA) into a physical block address (PBA) and uses the latter to access the data file within flash memory.
Stated differently, conventional computer systems are not configured to track continually changing physical locations of data files. Accordingly, each time a data file is changed, it is stored into a new physical location in the mass storage. Thus, mapping is required of the logical block address (LBA), i.e., the address where the computer system believes the data file is stored, to the physical block address (PBA), i.e., the actual location where the data file can be found in the mass storage unit. In the above-referenced patents, various algorithms are disclosed for determining where within the flash memory (mass storage) the next available free block is located for storing the data file. This function is performed by the space manager unit of the controller device. Space management techniques other than those discussed in the above patents may also be employed.
The correlation between logical block addresses and physical block addresses must be readily available to the controller for efficient storage or retrieval of data files. This correlation provides an essential mapping for finding files, data and the like within flash memory devices.
In systems of the prior art, information regarding the mapping of logical block addresses to physical block addresses is stored within volatile memory, such as RAM, which is located either within the controller device or outside of the controller device. Upon receiving a logical block address from the host, the controller accesses RAM to retrieve a physical block address in association with the host-provided logical block address and uses the retrieved physical block address to access the desired data file. The drawback with such systems is that volatile memory consumes a fair amount of semiconductor "real estate" thereby increasing the size of the controller (given that the volatile memory resides within the controller). Accordingly, costs associated with the manufacturing of such controller devices is similarly increased. If placed outside of the controller device, volatile memory again adds "real estate" to a board or card on which flash memory devices and the controller device reside, (this is in addition to the cost of the controller device itself) thereby increasing manufacturing costs.
Furthermore, use of volatile memory requires "shadow" storage of logical block address to physical block mapping. That is, when the digital system (or computer system by way of example) is turned off and no power is being supplied to the volatile memory, information stored therein including the LBA to PBA mapping, is lost thereby making retrieval of any data files impossible. It is for this reason that prior art systems using RAM to store the LBA-PBA mapping, store the same mapping information in a "shadow" location, which is generally a non-volatile storage area (such as in EEPROM or flash memory). The mapping information is accordingly preserved when power to the system is lost or temporarily interrupted. When power is again restored, the most recent mapping information prior to the loss of power is provided to and stored within volatile memory, i.e., RAM. As can be appreciated, this requires much overhead activity by the controller and reduces system efficiency and performance.
For the foregoing reasons, there is a need within digital systems, to efficiently determine the location of information that is either being retrieved or stored by a host within flash memory devices without foregoing system performance while minimizing the costs associated with the manufacturing of such digital systems.